package algs4.sort;

public class Merge
{
    /* Static Methods */
    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    public static void sort(Comparable[] a, int st, int ed) {
        // base case
        if (st >= ed) return;

        int mid = (st + ed) / 2;

        sort(a, st, mid);
        sort(a, mid + 1, ed);

        merge(a, st, mid, ed);
    }

    private static void merge(Comparable[] a, int st, int mid, int ed) {
        int          n = ed - st + 1;
        Comparable[] b = new Comparable[n];

        System.arraycopy(a, st, b, 0, n);

        int i = 0;
        int j = mid - st + 1;

        for (int k = st; k <= ed; k++) {
            if      (i > mid - st)         a[k] = b[j++];
            else if (j > ed - st)              a[k] = b[i++];
            else if (b[i].compareTo(b[j]) < 0) a[k] = b[i++];
            else                               a[k] = b[j++];
        }
    }
}
